//最后⼀块⽯头的重量II（medium):https://leetcode.cn/problems/last-stone-weight-ii/
class Solution
{
public:
	int lastStoneWeightII(vector<int>& stones)
	{
		// 1. 准备⼯作
		int sum = 0;
		for (auto x : stones)
		{
			sum += x;
		}
		int n = stones.size(), m = sum / 2;
		// 2. dp
		
		vector<vector<int>> dp(n + 1, vector<int>(m + 1));
		for (int i = 1; i <= n; i++)
		{
			for (int j = 0; j <= m; j++)
			{
				dp[i][j] = dp[i - 1][j];
				if (j >= stones[i - 1])
				{
					dp[i][j] = max(dp[i][j], dp[i - 1][j - stones[i - 1]] +stones[i - 1]);
				}
			}
		}
			
		// 3. 返回结果
		return sum - 2 * dp[n][m];
	}
};

//完全背包（medium）: https://www.nowcoder.com/practice/237ae40ea1e84d8980c1d5666d1c53bc?tpId=230&tqId=2032575&ru=/exam/oj&qru=/ta/dynamic-programming/question-ranking&sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196
#include <iostream>
#include <string.h>
using namespace std;
const int N = 1010;
int n, V, v[N], w[N];
int dp[N];
int main()
{
	// 读⼊数据
	cin >> n >> V;
	for (int i = 1; i <= n; i++)
	{
		cin >> v[i] >> w[i];
	}
		

	// 搞定第⼀问
	for (int i = 1; i <= n; i++)
	{
		for (int j = v[i]; j <= V; j++)
		{
			dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
		}
	}
		

	cout << dp[V] << endl;
	// 第⼆问
	memset(dp, 0, sizeof dp);
	for (int j = 1; j <= V; j++)
	{
		dp[j] = -0x3f3f3f3f;
	}

	for (int i = 1; i <= n; i++)
	{
		for (int j = v[i]; j <= V; j++)
		{
			dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
		}
	}
		

	cout << (dp[V] < 0 ? 0 : dp[V]) << endl;
	return 0;
}